SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Digraph realization problem</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Digraph realization problem</span></span>

</h1>

</header>

<p>The <b>digraph realization problem</b> is a <a href="Decision_problem" title="Decision problem">decision problem</a> in <a href="Graph_theory" title="Graph theory">graph theory</a>. Given pairs of nonnegative <a href="Integer" title="Integer">integers</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}</annotation>

</semantics>

</math></span><img src="./a97b189689f29f42ff7f4c330399c8b89474dd39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.674ex; height:2.843ex;" alt="{\displaystyle ((a_{1},b_{1}),\ldots ,(a_{n},b_{n}))}" loading="lazy"></span>, the problem asks whether there is a labeled <a href="Directed_graph" title="Directed graph">simple directed graph</a> such that each <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertex</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}}</annotation>

</semantics>

</math></span><img src="./7dffe5726650f6daac54829972a94f38eb8ec127.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.927ex; height:2.009ex;" alt="{\displaystyle v_{i}}" loading="lazy"></span> has <a href="Directed_graph" title="Directed graph">indegree</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}}</annotation>

</semantics>

</math></span><img src="./0bc77764b2e74e64a63341054fa90f3e07db275f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.029ex; height:2.009ex;" alt="{\displaystyle a_{i}}" loading="lazy"></span> and <a href="Directed_graph" title="Directed graph">outdegree</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}}</annotation>

</semantics>

</math></span><img src="./40a8c2db2990a53c683e75961826167c5adac7c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.797ex; height:2.509ex;" alt="{\displaystyle b_{i}}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Solutions">Solutions</h2></div>

<p>The problem belongs to the complexity class <a href="P_(complexity)" title="P (complexity)">P</a>. Two algorithms are known to prove that. The first approach is given by the <a href="Kleitman%E2%80%93Wang_algorithms" title="Kleitman–Wang algorithms">Kleitman–Wang algorithms</a> constructing a special solution with the use of a <a href="Recursion_(computer_science)" title="Recursion (computer science)">recursive algorithm</a>. The second one is a characterization by the <a href="Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem" title="Fulkerson–Chen–Anstee theorem">Fulkerson–Chen–Anstee theorem</a>, i.e. one has to validate the correctness of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> inequalities.

</p>

<div class="mw-heading mw-heading2"><h2 id="Other_Notations">Other Notations</h2></div>

<p>The problem can also be stated in terms of zero-one <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrices</a>. The connection can be seen if one realizes that each <a href="Directed_graph" title="Directed graph">directed graph</a> has an <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a> where the column sums and row sums correspond to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{1},\cdots ,a_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{1},\cdots ,a_{n})}</annotation>

</semantics>

</math></span><img src="./217e06b509d73739c0b46d298e2f0db3accda253.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.72ex; height:2.843ex;" alt="{\displaystyle (a_{1},\cdots ,a_{n})}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (b_{1},\ldots ,b_{n})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (b_{1},\ldots ,b_{n})}</annotation>

</semantics>

</math></span><img src="./c91c0e1b56ebc2709e7ab87063e877da6a1f037f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.255ex; height:2.843ex;" alt="{\displaystyle (b_{1},\ldots ,b_{n})}" loading="lazy"></span>. Note that the diagonal of the matrix only contains zeros. The problem is then often denoted by <i>0-1-matrices for given row and column sums</i>. In the classical literature the problem was sometimes stated in the context of <a href="Contingency_table" title="Contingency table">contingency tables</a> by <i>contingency tables with given marginals</i>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Related_problems">Related problems</h2></div>

<p>Similar problems describe the <a href="Degree_(graph_theory)" title="Degree (graph theory)">degree sequences</a> of <a href="Graph_theory" title="Graph theory">simple graphs</a>, <a href="Directed_graph" title="Directed graph">simple directed graphs</a> with <a href="Directed_graph" title="Directed graph">loops</a>, and <a href="Bipartite_graph" title="Bipartite graph">simple bipartite graphs</a>. The first problem is the so-called <a href="Graph_realization_problem" title="Graph realization problem">graph realization problem</a>. The second and third one are equivalent and are known as the <a href="Bipartite_realization_problem" title="Bipartite realization problem">bipartite realization problem</a>. <a href="#CITEREFChen1966">Chen (1966)</a> gives a characterization for <a href="Multigraph" title="Multigraph">directed multigraphs</a> with a bounded number of parallel arcs and loops to a given <a href="Directed_graph" title="Directed graph">degree sequence</a>. The additional constraint of the acyclicity of the directed graph is known as <i>dag realization</i>. <a href="#CITEREFNichterleinHartung2012">Nichterlein & Hartung (2012)</a> proved the <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-completeness</a> of this problem. <a href="#CITEREFBergerMüller-Hannemann2011">Berger & Müller-Hannemann (2011)</a> showed that the class of opposed sequences is in <a href="P_(complexity)" title="P (complexity)">P</a>. The problem <i>uniform sampling a directed graph to a fixed degree sequence</i> is to construct a solution for the digraph realization problem with the additional constraint that such each solution comes with the same probability. This problem was shown to be in <a href="Polynomial-time_approximation_scheme" title="Polynomial-time approximation scheme">FPTAS</a> for regular sequences by <a href="Catherine_Greenhill" title="Catherine Greenhill">Catherine Greenhill</a> (<a href="#CITEREFGreenhill2011">2011</a>) The general problem is still unsolved.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFChen1966" class="citation cs2">Chen, Wai-Kai (1966), "On the realization of a (<i>p</i>,<i>s</i>)-digraph with prescribed degrees", <i>Journal of the Franklin Institute</i>, <b>103</b>: <span class="nowrap">406–</span>422</cite></li>

<li><cite id="CITEREFNichterleinHartung2012" class="citation cs2">Nichterlein, André; Hartung, Sepp (2012), "NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs", <i>Journal of the Franklin Institute</i>, <b>7318</b>: <span class="nowrap">283–</span>292</cite></li>

<li><cite id="CITEREFBergerMüller-Hannemann2011" class="citation cs2">Berger, Annabell; Müller-Hannemann, Matthias (2011), "Dag Realizations of Directed Degree Sequences", <i>Proceedings of the 18th International Conference on Fundamentals of Computation Theory</i>: <span class="nowrap">264–</span>275</cite></li>

<li><cite id="CITEREFGreenhill2011" class="citation cs2"><a href="Catherine_Greenhill" title="Catherine Greenhill">Greenhill, Catherine</a> (2011), "A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs", <i>Electronic Journal of Combinatorics</i>, <b>18</b></cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-04" href="https://en.wikipedia.org/wiki/?title=Digraph_realization_problem&oldid=1273870764">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>